The ACO Seminar (2024–2025)

It is well known that, for any constant probability $p$, there exists a function $k(n)$ such that the independence number $\alpha$ of the binomial random graph $G_{n,p}$ is concentrated on two values; i.e., $\alpha(G_{n,p})$ equals $k(n)$ or $k(n)+1$ with high probability (that is, with probability converging to 1 as $n$ approaches infinity). This result was proved independently by Erdős and Bollobás and by Matula in the 1970's by using standard first and second moment techniques on the random variable counting the number of independent sets of a given size. Although not emphasized in the literature, this same strategy can be used to prove the above statement if $p = p(n) > n^{-\gamma}$ for any constant $\gamma < 1/3$. In this talk I will discuss the two consecutive results which, in combination, gives the extent of concentration of $\alpha(G_{n,p})$ for $p$ as small as $n^{-3/4 + \epsilon}$, in particular the latter paper, which establishes two-point concentration of $\alpha(G_{n,m})$ for $m > n^{5/4 + \epsilon}$ and gives a threshold at which $\alpha(G_{n,p})$ is no longer two-point concentrated. Joint work with Tom Bohman.